package java0323;

import java.util.Arrays;
import java.util.Stack;

// 排序
public class Test {
    // 稳定性
    // 插入排序，针对比较小的数组效率高，数组本身比较有序那么排序效率也高



    // 插排改进版，希尔排序  希尔：shell
    // 空间复杂度 时间复杂度O（1），不稳定排序
    // 先分组在排序，分组依靠分组系数 gap 例如gap = 3，一共三组，同一组元素的下标相差3
    // 针对每个分组插入排序，排完序调整 gap 为 2，再次分组插排……
    // 当 gap 较大的时候，每一组比较小，插排很快
    // 当 gap 较小的时候，每一组比较有序，插排也很快
    // 实际上 gap 的选择是 length/2 , length/4, ...... ,1
    public static void shellSort(int[] arr) {
        // 先指定 gap 序列
        int gap = arr.length / 2;
        while (gap >= 1) {
            _shellSort(arr, gap);
            gap = gap / 2;
        }
    }

    private static void _shellSort(int[] arr, int gap) {
        // 同一组元素的下标相差为 gap
        // 先取 0 组中的第一个元素，尝试往前插入排序
        // 先取 1 组中的第一个元素，尝试往前插入排序
        // 先取 2 组中的第一个元素，尝试往前插入排序
        // 先取 3 组中的第一个元素，尝试往前插入排序
        // ......所以这里是 bound++

        for (int bound = gap; bound < arr.length; bound++) {
            // 比较搬运,都是局限在当前组内的 bound - gap
            int v = arr[bound];
            // 从同组的前一个元素开始比较
            int cur = bound - gap;
            for (; cur >= 0; cur -= gap) {
                if (arr[cur] > v) {
                    // 搬运
                    arr[cur + gap] = arr[cur];
                }else {
                    break;
                }
            }
            arr[cur + gap] = v;
        }
    }

    // 选择排序：打擂台的方式每次寻找待排序区间的最小值放到待排区间的最开始的位置
    // 时间复杂度 O(N^2),空间复杂度 O(1), 不稳定的
    public static void selectSort(int[] arr) {
        // [0,bound) 是已排序区间 [bound,arr.length) 是未排序区间

        int bound = 0;
        for (; bound < arr.length; bound++) {
            // 这里就是打擂台的过程
            for (int cur = bound + 1; cur < arr.length; cur++) {
                if (arr[cur] < arr[bound]) {
                    // 交换
                    swap(arr, cur, bound);
                }
            }
        }
    }

    private static void swap(int[] arr, int cur, int bound) {
        int tmp = arr[cur];
        arr[cur] = arr[bound];
        arr[bound] = tmp;
    }

    // 堆排序
    // 其实也是一种选择排序，是它的一种优化
    // 直观上，我们可以建立一个小堆，循环N次，得到一个有序的序列，但是这个不是原地排序
    // 所以我们建立一个大堆，把堆顶元素即当前的最大值和数组的最后一个元素交换，这时候最大值在末尾（已排序区间在后面），
    // 前面的部分从0开始向下调整，调整完毕后又是一个堆，取出堆顶元素（未排序区间的最大值）（堆元素减一）和未排序区间的最后一个元素交换，
    // 时间复杂度由循环提供 O(NlogN) 空间复杂度O(1) 不稳定的
    public static void heapSort(int[] arr) {
        // 建堆
        createHeap(arr);
        // 循环进行交换堆顶元素和堆的最后一个元素，并且删除该元素
        int heapSize = arr.length;
        for (int i = 0; i < arr.length; i++) {
            swap(arr, 0, heapSize - 1);
            heapSize--;
            shiftDown(arr, heapSize, 0);
        }
    }

    // 建堆是 O(N)
    private static void createHeap(int[] arr) {
        for (int i = (arr.length - 1 - 1) / 2; i >= 0; i--) {
            shiftDown(arr, arr.length, i);
        }
    }

    // 向下调整是 O(logN)
    private static void shiftDown(int[] arr, int size, int index) {
        int parent = index;
        int child = 2 * parent + 1;
        while (child < size) {
            // 判断是否有右孩子且右孩子是两个孩子里面的较大值，调整child的指向
            if (child + 1 < size && arr[child + 1] > arr[child]){
                child = child + 1;
            }
            if (arr[parent] < arr[child]) {
                swap(arr, parent, child);
            }else {
                break;
            }
            parent = child;
            child = 2 * parent + 1;
        }
    }

    // 冒泡排序
    // 时间复杂度 O(N^2) 空间复杂度 O(1) 稳定的
    public static void bubbleSort(int[] arr) {
        // [0,bound)是已排序区间
        int bound = 0;
        for (; bound < arr.length; bound++) {
            for (int index = arr.length - 1; index > bound; index--) {
                if (arr[index] < arr[index - 1]) {
                    swap(arr, index, index - 1);
                }
             }
        }
    }

    // 快速排序
    // 先筛选出一个基准值，将数组整理成左边比基准值都小右侧比基准值都大的结果
    // 如何实现？两个下标left和right，left找到比基准值大的，right找一个比基准值小的交换
    // 最坏时间复杂度为O(N^2) 平均为O(NlogN)
    // 最坏空间复杂度为O(N)   平均为O(logN)
    // 不稳定
    // 优化手段，三数取中的方法
    // 如果数组很大，递归就很深，如果待处理的区间比较小了可以不进行递归而选择插入排序
    // 如果递归深度已经达到一定程度了，但是区间的元素数目还是很多，可以借助堆排序
    public static void quickSort(int[] arr) {
        // 用辅助方法递归，表示对那个区间整理，这个区间是双闭区间
        _quickSort(arr, 0, arr.length - 1);
    }

    private static void _quickSort(int[] arr, int left, int right) {
        if (left == right) {
            return;
        }
        // 使用这个方法整理，返回 left 和 right 重合的位置

        int index = partition(arr, left, right);
        _quickSort(arr, left, index - 1);
        _quickSort(arr, index + 1, right);
    }

    private static int partition(int[] arr, int left, int right) {
        // 选取基准值为最右测元素
        int v = arr[right];
        int i = left;
        int j = right;
        while (i < j) {
            //
            while (i < j && arr[i] <= v) {
                i++;
            }
            while (i < j && arr[j] >= v) {
                j--;
            }
            swap(arr, i, j);
        }
        // 如果发现重叠了,此时就要把基准值元素和重叠位置的元素交换
        swap(arr, i, right);
        return i;
    }

//    public static void quickSortByLoop(int[] arr) {
//        // 创建一个栈，栈里面存放要处理的区间
//        Stack<Integer> stack = new Stack<>();
//        // 把第一组要处理的区间入栈
//        stack.push(0);
//        stack.push(arr.length - 1);
//        // 循环取栈顶元素，进行 partition 操作
//        while (!stack.isEmpty()) {
//            int end = stack.pop();
//            int beg = stack.pop();
//            if ()
//        }
//    }

    public static void main(String[] args) {
//        int[] arr = {9,5,2,7,6,4,8};
////        shellSort(arr);
////        selectSort(arr);
////        heapSort(arr);
////        bubbleSort(arr);
//        quickSort(arr);
//        System.out.println(Arrays.toString(arr));

    }
}
